package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: ZhouBert
 * @date: 2020/11/25
 * @description: 二叉树的深度（深度=高度，也就是求 高度）
 * https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
 * （要求用递归和迭代 两种方法）
 */
public class A_剑指_Offer_55_I_二叉树的深度 {

	/**
	 * 递归解法
	 * 分析：
	 * 1.假设有个方法可以求得该节点的高度：f(TreeNode node);
	 * 2.根据具体模拟，可得：f(node)=Math.max(f(node.left),f(node.right))+1
	 * 3.现在对于递推公式，已经有了【递归条件】，就差【终止条件】了：
	 * -【终止条件】：if	 left==null && right==null -> 1
	 *
	 * @param root
	 * @return
	 */
	public static int maxDepthByRecursive(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return getHeight(root);
	}

	public static int getHeight(TreeNode node) {
		if (node == null) {
			return 0;
		}
		//终止条件
		if (node.left == null && node.right == null) {
			return 1;
		}
		return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
	}

	/**
	 * 迭代解法
	 * 跟层次遍历类似
	 *
	 * @param root
	 * @return
	 */
	public static int maxDepthByIteration(TreeNode root) {
		if (root == null) {
			return 0;
		}
		//
		int depth = 0;
		Queue<TreeNode> queue = new LinkedList();
		TreeNode cur = root;
		queue.offer(cur);
		while (!queue.isEmpty()) {
			int tempSize = queue.size();
			for (int i = 0; i < tempSize; i++) {
				cur = queue.poll();
				if (cur.left != null) {
					queue.offer(cur.left);
				}
				if (cur.right != null) {
					queue.offer(cur.right);
				}
			}
			depth++;
		}
		return depth;
	}


	public static void main(String[] args) {
		TreeNode root = new TreeNode(3);
		root.left = new TreeNode(9);
		root.right = new TreeNode(20);
		root.right.left = new TreeNode(15);
		root.right.right = new TreeNode(7);

		int depth = maxDepthByIteration(root);
		System.out.println("depth = " + depth);

		int depth2 = maxDepthByRecursive(root);
		System.out.println("depth = " + depth2);
	}
}
